
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Sort {
    //直接插入排序
    /*最外层for循环，第二个元素先放进tmp
    * 最里层循环，i的前一个元素与tmp比较，如果该元素大于tmp，把该元素赋给该元素的后一个位置（j+1）
    * 赋值完成j继续往前走，直到j<0或者j位置上的元素小于tmp
    * */
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j =i-1;//j=i-1意味着第一张牌默认有序
            for ( ; j >= 0; j--) {//进入该循环，tmp的值一直不变
                if (arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else {
                    //arr[j+1] = tmp;
                    //放到j+1下标是因为此时是用j下标的值与tmp比较
                    break;//如果此时j下标的值<tmp,意味着前面的数必然小于tmp，跳出循环
                }
            }
            //此时j+1的位置需要填充，把tmp给arr[j+1]
        arr[j+1] = tmp;
        }
    }
    //选择排序自己练习
    /*时间复杂度 n^2
    * 数据趋于有序，时间复杂度 n
    * 数据基本有序，建议使用选择插入排序
    * 空间复杂度 1
    * 稳定*/
    public static void InsertSort(int[] arr){
        for (int i=1; i<arr.length;i++ ){
            int tmp=arr[i];
            int j=i-1;
            for (; j >= 0; j--) {
                if (arr[j]>tmp){// arr[j]>arr[j+1]这种情况不可取，因为当遇到arr[j]<arr[j+1]的时候，直接跳出循环导致前面元素没有参与比较
                    arr[j+1]=arr[j];
                }else {
                    //arr[j+1]=arr[j];
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }
    /*
    * 希尔排序
    * 时间复杂度O（N^1.3）~O(N^1.5)
    * 不稳定*/
    public static void ShellSort(int[] arr){
        int gap=arr.length;
        while(gap>1){
            gap /= 2;//当gap==2时，gap=2/2==1,刚好进行最后一次分组
            Shell1(arr,gap);
        }
    }
    //插入排序
    private static void Shell(int[] arr,int gap){
        for (int i = gap; i < arr.length; i++) {
            int tmp=arr[i];
            int j = i-gap;
            for (; j >=0 ; j-=gap) {
                if (arr[j]>tmp){
                    arr[i]=arr[j];
                }else {
                    arr[j+gap]=tmp;
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }
    //希尔排序自己练习
    private static void Shell1(int[] arr,int gap){
        for (int i = gap; i < arr.length; i++) {
            int tmp=arr[i];
            int j=i-gap;
            for (; j >= 0; j-=gap) {
                if (arr[j]>tmp){//arr[j]>arr[j+1]
                    arr[j+gap]=arr[j];
                }else {
                    arr[j+gap]=tmp;
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }
    /*选择排序
    * 不稳定
    * 时间复杂度O（n^2）*/
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minIndex=i;
            //在待排数组中找到最小元素的下标
            int j = i+1;
            for (; j < arr.length; j++) {
                if (arr[minIndex]>arr[j]){
                    minIndex=j;
                }
            }
            //在待排元素中没找到或遍历完后
            //假如在待排元素中无找到最小元素，则minIndex依然为i
            swap(arr,i,j);
        }
    }
    private static void swap(int[] arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    //选择排序2
    public static void SelectSort2(int[] arr){
        int left=0;
        int right= arr.length-1;

        while (left < right){
            int minIndex=left;
            int maxIndex=left;
            for (int i = left+1; i <= right; i++) {
                if (arr[minIndex]>arr[i]){
                    minIndex=i;
                }if (arr[maxIndex]<arr[i]){
                    maxIndex=i;
                }
            }
            swap(arr,minIndex,left);
            //假如maxIndex没有更新过，依然是left，意味着最大值就在left位置
            // 此时需要注意跟踪最大值交换的位置
            if (maxIndex==left){
                //此时的minIndex下标为交换过的最大值下标
                maxIndex=minIndex;
            }
            swap(arr,maxIndex,right);

            left++;
            right--;
        }
    }
    //快速排序
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }
    //
    private static void quick(int[] arr,int start,int end){
        if (start >= end)
            return;
        if (end-start+1<=14){
            //减少递归次数
            insertSort2(arr,start,end);
            return;
        }
        //获取中间的元素
        int index=midtree(arr,start,end);
        swap(arr,index,start);
        //获取基准值下标
        int pivot=partition(arr,start,end);
        quick(arr,start,pivot-1);
        quick(arr,pivot+1,end);
    }
    //优化后的选择插入排序
    public static void insertSort2(int[] arr,int left,int right){
        for (int i = left+1; i <= right; i++) {
            int tmp = arr[i];
            int j =i-1;
            for ( ; j >= left; j--) {//进入该循环，tmp的值一直不变
                if (arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else {
                    //arr[j+1] = tmp;
                    //放到j+1下标是因为此时是用j下标的值与tmp比较
                    break;//如果此时j下标的值<tmp,意味着前面的数必然小于tmp，跳出循环
                }
            }
            //此时j+1的位置需要填充，把tmp给arr[j+1]
            arr[j+1] = tmp;
        }
    }
    //获取基准值并划分、排序(挖坑法)
    private static int partition1(int[] arr,int left,int right){
        int tmp=arr[left];
        while (left<right){
            while (left<right&&arr[right]>=tmp){
                //比tmp大就继续往前走
                right--;
            }
            //上面第一个循环走完，right下标的元素为比tmp小的元素
            arr[left]=arr[right];
            //在左边找比tmp大的值
            while (left<right&&arr[left]<=tmp){
                //比tmp小就继续往后走
                left++;
            }
            //运行到这里left下标的元素比tmp大
            arr[right]=arr[left];
        }
        arr[left]=tmp;//运行到这里left==right，把tmp的值给left下标，或者right下标
        return left;
    }
    //霍尔法快速排序
    private static int partition2(int[] arr,int left,int right){
        int tmp=arr[left];
        int i=left;
        while (left<right){
            while (left<right&&arr[right]>=tmp){
            right--;
            }
            while(left<right&&arr[left]<=tmp){
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,left,i);
        return left;
    }
    //前后指针
    private static int partition(int[] arr,int left,int right){
        int prev=left;
        int cur=left+1;
        while (cur<=right){
            if (arr[cur]<arr[left]&&arr[++prev]!=arr[cur]){
                swap(arr,cur,prev);
            }
            cur++;
        }
        swap(arr,prev,left);
        return prev;
    }
    //优化快速排序
    //三数取中法
    private static int midtree(int[] arr,int left,int right){
        int mid=(left+right)/2;
        if (arr[left]<arr[right]){
            if (arr[mid]<arr[left]){
                return left;
            }else if (arr[right]<arr[mid]){
                return right;
            }
            else{
                return mid;
            }
        } else  {
            if (arr[mid]<arr[right]) {
                return right;
            } else if (arr[left]<arr[mid]) {
                return left;
            }else {
                return mid;
            }
        }
    }
    //非递归实现快速排序
    public static void quickSort2(int[] arr){
        Deque<Integer> stack=new LinkedList<>();
        int left=0;
        int right=arr.length-1;
        int pivot=partition1(arr,left,right);
        if (pivot>left+1){//左边有两个元素
            stack.push(left);
            stack.push(pivot-1);
        }
        if (pivot<right-1){//右边有两个元素
            stack.push(pivot+1);
            stack.push(right);
         }
        while (!stack.isEmpty()){
             right=stack.pop();
             left=stack.pop();
             pivot=partition1(arr,left,right);
             if (pivot>left+1){//左边有两个元素
                stack.push(left);
                stack.push(pivot-1);
             }
             if (pivot<right-1){//右边有两个元素
                stack.push(pivot+1);
                stack.push(right);
             }
        }
    }
    //归并排序
    public static void mergeSort(int[] arr){
        mergeSortFunc(arr,0,arr.length-1);
    }
    //递归分解
    public static void mergeSortFunc(int[] arr,int left,int right){
        if (left>=right){
            return ;
        }
        int mid=(left+right)/2;
        mergeSortFunc(arr,left,mid);
        mergeSortFunc(arr,mid+1,right);
        merge(arr,left,right,mid);
    }
    //合并
    private static void merge(int[] arr,int start,int end,int mid){
        int s1=start;
        int s2=mid+1;
        int[] tmp=new int[end-start+1];
        int k=0;//tmp数组下标
        while (s1<=mid&&s2<=end){
            if (arr[s1]<=arr[s2]){
                tmp[k++]=arr[s1++];
            }else {
                tmp[k++]=arr[s2++];
            }
        }
        while (s1<=mid){
            //说明第一段还有数据
            tmp[k++]=arr[s1++];
        }
        while (s2<=end){
            //说明第二段还有数据
            tmp[k++]=arr[s2++];
        }
        for (int i=0;i<tmp.length;i++){
            arr[i+start]=tmp[i];
        }
    }
    //非递归实现归并排序
    public static void mergeSort1(int[] arr){
        int gap=1;
        while (gap<arr.length){
            for (int i=0;i<arr.length;i+=gap*2){
                int left=i;
                int mid=left+gap-1;//有可能越界
                if (mid>=arr.length){
                    mid=arr.length-1;
                }
                int right=mid+gap;
                if (right>=arr.length){
                    right=arr.length-1;
                }
                merge(arr,left,right,mid);
            }
            gap*=2;
        }
    }
}

